package demo.practice;
import java.util.Map;
import javax.net.SocketFactory;

import demo.practice.bfs.P127;

import java.util.*;

public class P126 {

    class Trie {
        Map<Character, Trie> child = new HashMap<>();
        int size;

        Trie(int size) {
            this.size = size;
        }

        Trie() {

        }

        String word;

        public void insert(String word) {
            if (word == null || word.length() != size)
                return;
            Trie cur = this;
            for (char c : word.toCharArray()) {
                if (cur.child.get(c) == null) {
                    cur.child.put(c, new Trie());
                }
                cur = cur.child.get(c);
            }
            cur.word = word;
        }


        public List<String> regex(String word) {
            //找出只有一个位置不同的单词
            List<String> list = new ArrayList<>();
            char[] chars = word.toCharArray();
            for (int j = 0; j < size; j++) {
                Trie cur = this;

                for (int i = 0; i < chars.length; i++) {
                    //第i个位置不匹配
                    if (i != j) {
                        if (cur.child.get(chars[i]) != null) {
                            cur = cur.child.get(chars[i]);
                        } else {
                            break;
                        }
                    } else {
                        if (i == chars.length - 1) {
                            for (Map.Entry<Character, Trie> en : cur.child.entrySet()) {
                                if (en.getKey() != chars[i]) {
                                    list.add(en.getValue().word);
                                }

                            }
                        }else{
                            for (Map.Entry<Character, Trie> en : cur.child.entrySet()) {
                                if (en.getKey() != chars[i]) {
                                    String match = match(chars, i + 1, en.getValue());
                                    if (match != null)
                                        list.add(match);
                                }
                            }
                        }


                    }
                }
            }

            return list;
        }

        public String match(char[] chars, int i, Trie t) {
            Trie cur = t;
            for (; i < chars.length; i++) {
                char c = chars[i];
                if (cur.child.get(c) != null) {
                    cur = cur.child.get(c);
                } else {
                    return null;
                }
            }
            return cur.word;
        }


    }

    public static void main(String[] args) {
        P126 p126 = new P126();
        List<List<String>> i = p126.findLadders("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        System.out.println(i);

    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        List<List<String>> res = new ArrayList<>();
        if (beginWord == null || endWord == null || beginWord.length() != endWord.length() || beginWord.equals(endWord))
            return res;

        Queue<Object[]> queue = new LinkedList<>();
        ArrayList<String> path = new ArrayList<>();
        path.add(beginWord);
        queue.add(new Object[]{beginWord, path});

        Trie trie = new Trie(beginWord.length());
        for (String s : wordList) {
            trie.insert(s);
        }

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        //int level = 0;


        while (!queue.isEmpty()) {
            int size = queue.size();
            //[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
            Set<String> vc  = new HashSet<>();
            while (size > 0) {

                Object[] poll = queue.poll();
                List<String> sc = (ArrayList<String>) poll[1];
                if (poll[0].equals(endWord))
                    res.add(sc);
                    // return level + 1;
                else {
                    List<String> regexs = trie.regex((String) poll[0]);
                    for (String regex : regexs) {
                        if (!visited.contains(regex)) {
                            ArrayList<String> sc2 = new ArrayList<>(sc);
                            sc2.add(regex);
                            queue.add(new Object[]{regex, sc2});
                            vc.add(regex);
                        }
                    }
                }
                size--;
            }
            visited.addAll(vc);

            if (!res.isEmpty())
                return res;
        }
        return res;
    }
}
